import copy
import sys
import time
from re import S
from time import sleep
from typing import List

from Board import Board
from Frame import Frame

"""
此模块用于定义实现算法的诸多数据结构
"""

MIN = -1000000000


class TreeNode:
    """
    用来表示棋盘的博弈树的节点
    """
    MAX_TIME = 15
    def __init__(self, red_player: int, blue_player: int, red_score: int, blue_score: int, current_player: int,
                 board: Board, parent: "TreeNode"):
        """
        blue_player:  蓝方玩家 int
        red_player:  红方玩家 int
        red_score:  红方得分 int
        blue_score:  红方得分 int
        current_player: 当前玩家
        board:  当前棋盘
        parent:  父节点
        new_score: 评估的需要的存储的分数
        step: 当前模拟的可用步数
        children: 子节点的列表为: TreeNode
        best_step: 将要返回的可下步数
        gen_step: 可达步骤从父节点到子节点
        create_nums: 子节点生成的个数
        """
        self.red_player = red_player
        self.blue_player = blue_player
        self.red_score = red_score
        self.blue_score = blue_score
        self.current_player = current_player
        self.board = copy.deepcopy(board)
        self.temp_board = copy.deepcopy(board)
        self.parent = parent
        self.new_score = -1000
        self.step = board.get_available_step(is_shuffle=False)
        self.children: List["TreeNode"] = []
        self.best_step = []
        self.gen_step = None
        self.utility = MIN
        self.create_nums = 0
        # 自己获利尽量大的时候修改
        self.alpha = -sys.maxsize
        # 使对手获利小的时候进行修改
        self.beta = sys.maxsize
        # 存放此节点为什么位置得来的
        self.local_step = []
        self.max_score = -1000
        self.min_score = 1000

        self.the_score = 0

    def get_children(self):
        if len(self.step) != 0:
            for i in self.step:
                dir = i[0]
                x = i[1]
                y = i[2]
                self.board.set_line(self.current_player, dir, x, y)
                score = self.board.check_box(self.current_player)
                # 没分说明要换手，子节点当前玩家要变
                if score == 0:
                    if self.current_player == self.red_player:
                        # 子节点的当前玩家应该为blue
                        child = TreeNode(self.red_player, self.blue_player, self.red_score, self.blue_score, self.blue_player, self.board, self)
                    else:
                        child = TreeNode(self.red_player, self.blue_player, self.red_score, self.blue_score, self.red_player, self.board, self)
                    self.children.append(child)
                # 有分不换手，所以子节点的当前玩家不变，但分要改变
                else:
                    if self.current_player == self.red_player:
                        child = TreeNode(self.red_player, self.blue_player, self.red_score + score, self.blue_score, self.current_player, self.board, self)
                    else:
                        child = TreeNode(self.red_player, self.blue_player, self.red_score, self.blue_score + score, self.current_player, self.board, self)
                    self.children.append(child)
                # 每循环一次都需要把棋盘归位，最总棋盘总是父节点的棋盘
                self.board = self.temp_board
        else:
            # 如果可用步数没了说明游戏结束，不再添加子节点
            # 解析的时候判断 END 即可
            self.children.append('END')

    def get_best_step(self):
        pass



class TreeNode:
    """
    用来表示棋盘的博弈树的节点
    """
    def __init__(self, red_player: int, blue_player: int, red_score: int, blue_score: int, current_player: int, board: Board, parent: "TreeNode"):
        """
        :param red_player:  红方玩家 int
        :param blue_player:  蓝方玩家 int
        :param red_score:  红方得分 int
        :param blue_score:  红方得分 int
        :param current_player: 当前玩家
        :param board:  当前棋盘
        :param parent:  父节点
        """
        self.red_player = red_player
        self.blue_player = blue_player
        self.red_score = red_score
        self.blue_score = blue_score
        self.current_player = current_player
        self.board = copy.deepcopy(board)
        self.temp_board = copy.deepcopy(board)
        self.parent = parent
        self.new_score = 0
        self.step = board.get_available_step(is_shuffle=True)
        self.children = []
        self.best_step = []

        self.miniScore=[]
        self.TreeStep=[]

    def get_children(self):
        if len(self.step) != 0:
            for i in self.step:
                dir = i[0]
                x = i[1]
                y = i[2]
                score = 0
                self.board.set_line(self.current_player, dir, x, y)
                score = self.board.check_box(self.current_player)
                if score == 0:
                    if self.current_player == self.red_player:
                        # 子节点的当前玩家应该为blue
                        child = TreeNode(self.red_player, self.blue_player, self.red_score, self.blue_score,
                                         self.blue_player, self.board, self)
                    else:
                        child = TreeNode(self.red_player, self.blue_player, self.red_score, self.blue_score,
                                         self.red_player, self.board, self)
                    # child.board.print_line()
                    # print('------')
                    child.local_step.append(i)
                    self.children.append(child)
                    self.create_nums += 1
                # 有分不换手，所以子节点的当前玩家不变，但分要改变
                else:
                    if self.current_player == self.red_player:
                        child = TreeNode(self.red_player, self.blue_player, self.red_score + score, self.blue_score,
                                         self.current_player, self.board, self)
                    else:
                        child = TreeNode(self.red_player, self.blue_player, self.red_score, self.blue_score + score,
                                         self.current_player, self.board, self)
                    # child.board.print_line()
                    # print('------')
                    child.local_step.append(i)
                    self.children.append(child)
                    self.create_nums += 1
                # 每循环一次都需要把棋盘归位，最总棋盘总是父节点的棋盘
                self.board = copy.deepcopy(self.temp_board)
        else:
            # 如果可用步数没了说明游戏结束，不再添加子节点
            # 解析的时候判断 END 即可
            self.children.append('END')

    def is_terminal(self):
        """
        判断当前节点是否是终极节点
        """

        if len(self.children) == 0 or self.children[0] == 'END':
            return True
        else:
            return False

    def get_next_gen(self):
        """
        @author: hzx
        得到子节点
        """
        if len(self.step) != 0:
            for i in self.step:
                dir = i[0]
                x = i[1]
                y = i[2]
                score = 0
                self.board.set_line(self.current_player, dir, x, y)
                # 记录父节点到子节点的可达步
                self.gen_step = i
                score = self.board.check_box(self.current_player)
                # ******
                # 没分说明要换手，子节点当前玩家要变
                if score == 0:
                    if self.current_player == self.red_player:
                        # 子节点的当前玩家应该为blue
                        child = TreeNode(self.red_player, self.blue_player, self.red_score, self.blue_score,
                                         self.blue_player, self.board, self)
                    else:
                        child = TreeNode(self.red_player, self.blue_player, self.red_score, self.blue_score,
                                         self.red_player, self.board, self)
                    # child.board.print_line()
                    # print('------')
                    self.children.append(child)
                # 有分不换手，所以子节点的当前玩家不变，但分要改变
                else:
                    if self.current_player == self.red_player:
                        child = TreeNode(self.red_player, self.blue_player, self.red_score + score, self.blue_score,
                                         self.current_player, self.board, self)
                    else:
                        child = TreeNode(self.red_player, self.blue_player, self.red_score, self.blue_score + score,
                                         self.current_player, self.board, self)
                    # child.board.print_line()
                    # print('------')
                    self.children.append(child)
                # 每循环一次都需要把棋盘归位，最总棋盘总是父节点的棋盘
                self.board = copy.deepcopy(self.temp_board)
        else:
            # 如果可用步数没了说明游戏结束，不再添加子节点
            # 解析的时候判断 END 即可
            self.children.append('END')
    # def create_step(self,i):
    #
    #     self.miniScore[i]=0
    #     lc=self.step
    #     the_step=lc[i]
    #     self.TreeStep[i].append(the_step)
    #     del lc[i]
    #     if self.board.check_box():


    # 对于当前棋盘的五层子树生成
    def control_deep(self):
        t1 = time.time()
        print('开始搜索模拟')
        # 尽量减少不必要的搜索
        # 尝试进行评估缩小不必的搜索范围
        # 第一层的子树生成
        self.get_children()
        # 判断子树是否已经为空
        if self.children[0] == 'END':
            return
        else:
            # 进行第二层子树的遍历生成
            for i in range(0, len(self.children)):
                self.children[i].get_children()
                # 判断子树是否为空
                if self.children[i].children[0] == 'END':
                    return
                else:
                    # 进行第三层子树的遍历生成
                    for j in range(0, len(self.children[i].children)):
                        self.children[i].children[j].get_children()
                        score = self.children[i].children[j].get_score()
                        self.parent_score(self.children[i].children[j], score)
                        self.parent_score(self.children[i], score)
                        # 判断子树是否为空
                        if self.children[i].children[j].children[0] == 'END':
                            self.create_nums = self.children[i].create_nums
                            return
                        else:
                            #  进行第4层子树遍历生成
                            for k in range(0, len(self.children[i].children[j].children)):
                                self.children[i].children[j].children[k].get_children()
                                score = self.children[i].children[j].children[k].get_score()
                                self.parent_score(self.children[i].children[j].children[k], score)
                                self.parent_score(self.children[i].children[j], score)
                                self.parent_score(self.children[i], score)
                                # 判断子树是否为空
                                if self.children[i].children[j].children[k].children[0] == 'END':
                                    self.create_nums = self.children[i].create_nums * self.children[i].children[
                                        j].create_nums
                                    return
                                else:
                                    # 进行第五层的子树遍历生成
                                    for l in range(0, len(self.children[i].children[j].children[k].children)):
                                        self.children[i].children[j].children[k].children[l].get_children()
                                        score = self.children[i].children[j].children[k].children[l].get_score()
                                        # 将分逐层传递
                                        # 这里会直接传递到最上层，也就是根节点的子节点上
                                        self.parent_score(self.children[i].children[j].children[k].children[l], score)
                                        self.parent_score(self.children[i].children[j].children[k], score)
                                        self.parent_score(self.children[i].children[j], score)
                                        self.parent_score(self.children[i], score)
                                        # 初始的时候，我们将对第4层第一个节点生成的子节点进行得出第4层的beta
                                        # 确定beta后，我们可以知道第3成的alpha值，表示至少第3层的收益都大于beta
                                        if i == 0 and j == 0 and k == 0:
                                            if self.children[i].children[j].children[k].current_player == self.red_player:
                                                # 由于上层是对手的
                                                # 直到更新出最小的
                                                self.children[i].children[j].children[k].beta = self.children[i].children[j].children[k].min_score
                                                self.children[i].children[j].alpha = self.children[i].children[j].children[k].min_score
                                                # t同时更行i层的beta值
                                                self.children[i].beta = self.children[i].children[j].min_score
                                            else:
                                                # 由于上层是自己的
                                                # 直到更新出最大的
                                                self.children[i].children[j].children[k].beta = self.children[i].children[j].children[k].max_score
                                                self.children[i].children[j].alpha = self.children[i].children[j].children[k].max_score
                                                # t同时更行i层的beta值
                                                self.children[i].beta = self.children[i].children[j].max_score

                                        else:
                                            # 对于第4成的第二个节点以后，我们需要判断是否需要改变alpha值和beta值
                                            # 若改变，就进行改变第三层的alpha值
                                            if self.children[i].children[j].current_player == self.red_player:
                                                if score < self.children[i].children[j].children[k].beta:
                                                    self.children[i].children[j].children[k].beta = score
                                                    self.children[i].children[j].alpha = score
                                                else:
                                                    break
                                            else:
                                                if score > self.children[i].children[j].children[k].beta:
                                                    self.children[i].children[j].children[k].beta = score
                                                    self.children[i].children[j].alpha = score
                                                else:
                                                    break
                                t2 = time.time()
                                if t2 - t1 >= TreeNode.MAX_TIME:
                                    print('结束')
                                    print('搜索时间:%s秒' % (t2 - t1))
                                    return
                                # 这里对第4层的分和第3层的比较看是有剪枝的必要
                                if j != 0:
                                    # 如果有最大的分大于当前alpha的进行alpha更新，否则没必要进行搜索
                                    if self.children[i].children[j].current_player == self.blue_player:
                                        if self.children[i].children[j].children[k].max_score > self.children[i].children[
                                            j].alpha:
                                            self.children[i].children[j].alpha = self.children[i].children[j].children[
                                                k].max_score
                                        else:
                                            break
                                    else:
                                        if self.children[i].children[j].children[k].min_score < self.children[i].children[j].alpha:
                                            self.children[i].children[j].alpha = self.children[i].children[j].children[k].min_score
                                        else:
                                            break
                        t2 = time.time()
                        if t2 - t1 >= TreeNode.MAX_TIME:
                            print('结束')
                            print('搜索时间:%s秒' % (t2 - t1))
                            return
                        if i != 0:
                            if self.children[i].current_player == self.red_player:
                                if self.children[i].children[j].min_score < self.children[i].beta:
                                    self.children[i].beta = self.children[i].children[j].min_score
                                else:
                                    break
                            else:
                                if self.children[i].children[j].max_score > self.children[i].beta:
                                    self.children[i].beta = self.children[i].children[j].max_score
                                else:
                                    break
        print('结束')
        t2 = time.time()
        print('搜索时间:%s秒' % (t2 - t1))
        return

    # 传递分数
    def parent_score(self, node: "TreeNode", score):
        if score > node.parent.max_score:
            node.parent.max_score = score
        if score < node.parent.min_score:
            node.parent.min_score = score

    # 得到最佳的步数
    def get_best_step(self):
        # for i in range(len(self.step)):
        #     self.TreeStep.append([])
        #     self.create_step(i)
        pass
        max = -1000
        for i in self.children:
            if i.max_score >= max:
                step = i.local_step[0]
                dir = step[0]
                x = step[1]
                y = step[2]
                self.best_step.append((dir, x, y))
        return self.best_step

    # 迭代进行生成模拟子树
    def generate_tree(self, node: "TreeNode", high: int):
        if high <= 0:
            return
        node.get_children()
        if len(node.children) == 0 or node.children[0] == "END":
            return
        else:
            for i in range(0, len(node.children)):
                node.children[i].generate_tree(node.children[i], high - 1)

    def gen_tree(self, node: "TreeNode", high):
        """生成完全子节点

        Args:
            node (TreeNode): root节点
            high (_type_): 高度
        """
        if high <= 0:
            return
        node.get_next_gen()
        if len(node.children) == 0 or node.children[0] == "END":
            return
        else:
            for i in range(0, len(node.children)):
                node.children[i].gen_tree(node.children[i], high - 1)

    # 评估函数
    def get_score(self):
        level_one = 20
        level_two = 1
        level_three = 15
        score = 0
        # 对于当前玩家局面的初始分数的评估
        if self.current_player == self.red_player:
            score = level_one * self.red_score - level_one * self.blue_score
        else:
            score = level_one * self.blue_score - level_one * self.red_score
        # 对于当前玩家后续得分的增减
        # 测试判断分
        # 在帮自己下
        if self.current_player == self.blue_player:
            score += level_three * self.board.get_box_count(3) - level_two * self.board.get_box_count(2)
        else:
            score -= level_three * self.board.get_box_count(3) - level_two * self.board.get_box_count(2)
        return score

    def evaluate_node(self, node: "TreeNode"):
        level_one = 20
        level_two = 1
        level_three = 15
        score = 0
        if node.current_player == node.red_player:
            score = level_one * node.red_score - level_two * node.blue_score
        else:
            score = level_one * node.blue_score - level_two * node.red_score
        if node.current_player == node.red_player:
            score += level_three * node.board.get_box_count(3) - level_two * node.board.get_box_count(2)
        else:
            score -= level_three * node.board.get_box_count(3) - level_two * node.board.get_box_count(2)
        return score

    # 打印模拟后的可用步数
    def print_step(self):
        print(self.step)

    #新添 miniScore=[]来判断我方相比得分，即我方得一分加，对方得一分减
    #新添 TreeStep=[] 来表示步伐树，列表装列表
    #这一步思想： 取其中来一步判断，递归，一直走到末尾，目前表示我方先走





class MCTreeNode(object):
    """mcts树中的节点

    """
    
    def __init__(self, frame: Frame, level, edge) -> None:
        self.board = frame.current_board
        self.turn = frame.current_round
        self.level = level
        self.edge = edge
        self.child = []
        
        


if __name__ == '__main__':
    board = Board()
    tree_test = TreeNode(1, 2, 0, 0, 1, board, None)
    tree_test.generate_tree(tree_test, 2)
    tree_test.print_step()
